﻿//神奇的字⺟（⼆）（哈希+字符串）
//https://ac.nowcoder.com/acm/problem/205832

//#include<iostream>
//using namespace std;
//
//int main()
//{
//    string s;
//    int hash[26] = { 0 };
//    char ret = 0;
//    int maxCount = 0;
//    while (cin >> s)
//    {
//        for (auto ch : s)
//        {
//            hash[ch - 'a']++;
//            if (hash[ch - 'a'] > maxCount)
//            {
//                maxCount = hash[ch - 'a'];
//                ret = ch;
//            }
//        }
//    }
//    cout << ret << endl;
//
//    return 0;
//}


//字符编码（哈夫曼编码）
//https://www.nowcoder.com/practice/c471efdbd33a4a979539a91170c9f1cb?tpId=128&tqId=33774&ru=/exam/oj

//#include <iostream>
//#include <queue>
//#include <vector>
//#include <string>
//using namespace std;
//
//int main() {
//    string s;
//    while (cin >> s)
//    {
//        int hash[300] = { 0 };
//        for (auto ch : s)
//            hash[ch]++;
//
//        priority_queue<int, vector<int>, greater<int>> heap;
//        for (auto cnt : hash)
//        {
//            if (cnt)
//                heap.push(cnt);
//        }
//
//        int ret = 0;
//        while (heap.size() > 1)
//        {
//            int t1 = heap.top(); heap.pop();
//            int t2 = heap.top(); heap.pop();
//            ret += t1 + t2;
//            heap.push(t1 + t2);
//        }
//        cout << ret << endl;
//    }
//    return 0;
//}


//最少的完全平⽅数（动态规划）
//https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04?tpId=230&tqId=40431&ru=/exam/oj

//dp[i][j] 从0-i中挑选，平方和等于j的最少数字
//dp[i][j]=min(dp[i-1][j],dp[i-1][j-i*i]+1)
//初始化：0x3f,dp[i][0]=0;
//空间优化 dp[j]=min(dp[j],dp[j-i*i]+1);正序遍历 dp[0]=0 j>=i*i j<=n;

//#include <iostream>
//#include <cstring>
//using namespace std;
//
//const int N = 1e4 + 5;
//int dp[N];
//int n;
//
//int main() {
//    cin >> n;
//    memset(dp, 0x3f, sizeof(dp));
//    dp[0] = 0;
//    for (int i = 1; i * i <= n; i++)
//    {
//        for (int j = i * i; j <= n; j++)
//            dp[j] = min(dp[j], dp[j - i * i] + 1);
//    }
//    cout << dp[n] << endl;
//    return 0;
//}